// @algorithm @lc id=46 lang=cpp 
// @title permutations


// @test([1,2,3])=[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
// @test([0,1])=[[0,1],[1,0]]
// @test([1])=[[1]]
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        function<void(int)> dfs = [&](int cur){
            if(cur==nums.size()){
                ans.push_back(nums);
                return;
            }
            for(int i=cur; i<nums.size(); i++){
                if(i!=cur)swap(nums[cur], nums[i]);
                dfs(cur+1);
                if(i!=cur)swap(nums[cur], nums[i]);
            }
        };
        dfs(0);
        return ans;
    }
};